package com.leetcode.algorithm.y22.m07;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 20. 有效的括号
 * 
 * https://leetcode.cn/problems/valid-parentheses/
 * 
 * @author jie.deng
 *
 */
class Question0020Solution01 {

	public boolean isValid(String s) {
		Deque<Character> stack = new ArrayDeque<>();
		int len = s.length();
		int idx = 0;
		while (idx < len) {
			char ch = s.charAt(idx);
			if (ch == '(' || ch == '{' || ch == '[') {
				stack.push(ch);
			} else {
				if (stack.isEmpty()) {
					return false;
				}
				char prev = stack.pop().charValue();
				if (!((ch == ')' && prev == '(') || (ch == '}' && prev == '{') || (ch == ']' && prev == '['))) {
					return false;
				}
			}
			idx++;
		}
		return stack.isEmpty();
	}

}